class Solution {
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0") return "0";
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int m = num1.size(), n = num2.size();

        vector<int> tmp(m + n - 1);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        int add = 0;
        int i = 0;
        string ret;
        while (i < tmp.size() || add)
        {
            if (i < tmp.size()) add += tmp[i];
            ret += (add % 10 + '0');
            add /= 10;
            i++;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
class Solution {
public:
    string addBinary(string a, string b)
    {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        string ret;
        int i = 0;
        int add = 0;
        while (i < a.size() || i < b.size() || add)
        {
            if (i < a.size()) add += a[i] - '0';
            if (i < b.size()) add += b[i] - '0';
            ret += (add % 2 + '0');
            add /= 2;
            i++;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = -1, len = 0;

        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (i == j) dp[i][j] = true;
                else if (i + 1 == j)
                {
                    if (s[i] == s[j]) dp[i][j] = true;
                }
                else
                {
                    if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && (j - i + 1 > len))
                {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, len);
    }
};